

#include <sudoku.h>
#include <matrix.h>

vm_matrix *_sdk_valid_positions(sudoku *sdk, int brow, int bcol, int num){

  /* Make sure the possibility lists are good. */
  int i, j;
  for ( i = 0; i < SDK_SIZE; i++){
    for ( j = 0; j < SDK_SIZE; j++){
      _sdk_square_possibilities(sdk, i, j);
    }
  }

  vm_matrix *pos = vm_make_matrix(3, 3);

#ifdef _DEBUG
  fprintf(stderr, "Generating possibility matrix: [%d:%d]\n", brow, bcol);
#endif 

  for ( i = 0; i < SDK_SUB_MTX_SIZE; i++){
    for ( j = 0; j < SDK_SUB_MTX_SIZE; j++){
      sdk_square *tmp = &SDK_ELEM(sdk, (SDK_SUB_MTX_SIZE * brow) + i,
				 (SDK_SUB_MTX_SIZE * bcol) + j);
#ifdef _DEBUG
      fprintf(stderr, "[%d:%d] ", i, j);
      _sdk_list_print_short_sum(&tmp->pos);
#endif
      if (sdk_list_get(&tmp->pos, num)){
	pos->data[i][j] = 1;
      }
    }
  }

#ifdef _DEBUG
  vm_print_matrix(pos, "");
#endif

  return pos;

}

int _sdk_flesh_sdk(sudoku *sdk){

  //fprintf(stderr, "[_sdk_flesh_sdk] Start mem: %ld\n", _sdk_memory);

  int fleshing = 1;
  int cur_sols = sdk_number_solutions(sdk);
  int start_sols = cur_sols;

  while (fleshing){

    //fprintf(stderr, "[_sdk_flesh_sdk] Mem at point A: %ld\n", _sdk_memory);

#ifdef _DEBUG
    fprintf(stderr, "[_sdk_flesh_sudoku] Generating possibility lists\n");
#endif

    int i, j;

    for ( i = 0; i < SDK_SIZE; i++){
      for ( j = 0; j < SDK_SIZE; j++){
	_sdk_square_possibilities(sdk, i, j);
      }
    }

    //fprintf(stderr, "[_sdk_flesh_sdk] Mem at point B: %ld\n", _sdk_memory);

#ifdef _DEBUG
    fprintf(stderr, "[_sdk_flesh_sudoku] Generated possibilities: ok\n");
#endif

    sdk_update_values(sdk);
    int tmp_sols = sdk_number_solutions(sdk);
    if (cur_sols == tmp_sols){ // We are done fleshing.
      fleshing = 0;
    }
    cur_sols = tmp_sols;

#ifdef _DEBUG
    fprintf(stderr, "[_sdk_flesh_sudoku] Number of solutions: %d\n", cur_sols);
#endif

  }

  return sdk_number_solutions(sdk) - start_sols;

}

void _sdk_hidden_singles_in_sub_mtx(sdk_sub_mtx_overlay *mtx){

  int i, j;

  for ( i = 0; i < SDK_SUB_MTX_SIZE; i++){
    for ( j = 0; j < SDK_SUB_MTX_SIZE; j++){

      //fprintf(stderr, "box num: [%d:%d] value: %d. ", 
	      //i, j, mtx->sdk_data[i][j]->value);
      //_sdk_list_print_short_sum(&mtx->sdk_data[i][j]->pos);

      if (mtx->sdk_data[i][j]->value) continue;
      
      /* Otherwise go through the other lists looking */
      /* for a number in this list.                   */
      
      //fprintf(stderr, "Square: [%d:%d]\n", i, j);

      sdk_elem *elem;
      SDK_LIST_TRAV((&mtx->sdk_data[i][j]->pos), elem){

	//fprintf(stderr, "  Looking for this hidden single: %d\n", elem->num);

	
	int p, q;
	int found = 0;

	for ( p = 0; p < SDK_SUB_MTX_SIZE; p++){
	  for ( q = 0; q < SDK_SUB_MTX_SIZE; q++){
	    if (p == i && q == j){
	      //fprintf(stderr, "[%d:%d] this is a dupe square\n", i, j);
	      continue; // dont count our selves.
	    }
	    //if (sdk_list_length(&mtx->sdk_data[p][q]->pos) == 1) continue;
	    if (sdk_list_get(&mtx->sdk_data[p][q]->pos, elem->num)){
	      found = 1;
	      p = SDK_SUB_MTX_SIZE; q = SDK_SUB_MTX_SIZE;
	    }
	  }
	}
	if (!found){ // This is a hidden single.
	  mtx->sdk_data[i][j]->value = elem->num;
	  break;
	}
      }
    }
  }

}

/*
 * This function finds and solves all hidden singles in the passed sudoku.
 */
int _sdk_solve_hidden_singles(sudoku *sdk){

  int solved;
  int start_solved = sdk_number_solutions(sdk);

  sdk_update_values(sdk);
  sdk_update_lists(sdk);

  while (1){

    solved = sdk_number_solutions(sdk);

    /* Iterate over the submatrices, then the rows, then the cols. */
    int i, j;
    for ( i = 0; i < SDK_SUB_MTX_SIZE; i++){
      for ( j = 0; j < SDK_SUB_MTX_SIZE; j++){
	//fprintf(stderr, "Solving box: [%d:%d]\n", i, j);
	sdk_sub_mtx_overlay *mtx = _sdk_sub_mtx_overlay(sdk, i, j);
	_sdk_hidden_singles_in_sub_mtx(mtx);
	_sdk_memory -= sizeof(sdk_sub_mtx_overlay);
	free(mtx); 
      }
    }

    sdk_update_values(sdk);
    sdk_update_lists(sdk);

    if (solved == sdk_number_solutions(sdk)){
      return sdk_number_solutions(sdk) - start_solved;
    }
  }

}

int sdk_solve(sudoku *sdk){


  _sdk_flesh_sdk(sdk);
  sdk_update_values(sdk);
  sdk_update_lists(sdk);
  
  if (sdk_full_sdk(sdk)){ // Assume the sudoku is solved if its full
    return 1;
  }

  int squares_solved = 0;

  while (1){
    squares_solved = _sdk_solve_hidden_singles(sdk);
    squares_solved += _sdk_flesh_sdk(sdk);

    sdk_update_values(sdk);
    sdk_update_lists(sdk);

    if (sdk_full_sdk(sdk)){
      return 1;
    }
    if (squares_solved == 0){
      return 0;
    }
  }

}

